home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 395_01 / avl / slapply.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-05  |  2.7 KB  |  93 lines
  1. /* implementation file for apply function for sorted list data
  2.    structure.  implemented as an AVL tree. */
  3.  
  4. #include "sortlist.h"
  5. #include "slintrnl.h"
  6.  
  7. typedef struct
  8.   {
  9.     /* apply function */
  10.     int (*apply)(void *elem, void *param);
  11.     /* second parameter to apply function */
  12.     void *param;
  13.     /* which branch to do first */
  14.     int first_branch;
  15.     /* starting key (may be null) */
  16.     void *start_key;
  17.     /* key - element compare function */
  18.     int (*k_e_compare)(const void *key, const void *elem);
  19.   }
  20. APPLY_PARAM;
  21.  
  22. /* visit each element in subtree after given start */
  23. static int do_apply
  24.   (
  25.     /* subtree to traverse */
  26.     void *tree,
  27.     /* other parameters */
  28.     APPLY_PARAM *ap
  29.   )
  30.   {
  31.     int r;
  32.  
  33.     if (!tree)
  34.       return(0);
  35.  
  36.     if (ap->start_key)
  37.       {
  38.     r = (*(ap->k_e_compare))(ap->start_key, ELEM_IN_NODE(tree));
  39.     if (ap->first_branch == GREATER_BRANCH)
  40.       r = -r;
  41.       }
  42.     else
  43.       r = -1;
  44.  
  45.     if (r <= 0)
  46.       {
  47.     if (r < 0)
  48.       r = do_apply(NODE(tree)->branch[ap->first_branch], ap);
  49.     if (!r)
  50.       r = (*(ap->apply))(ELEM_IN_NODE(tree), ap->param);
  51.     if (r)
  52.       return(r);
  53.       }
  54.     return(do_apply(NODE(tree)->branch[OTHER(ap->first_branch)], ap));
  55.   }
  56.  
  57. /* visit each element in the list in ascending or descending order.
  58.    call a given function with the element being visited as a parameter.
  59.    if the given function returns non-zero, the traversal is interrupted.
  60.    returns the result of the last call to the given function, or 0 if
  61.    no elements are visited */
  62. int apply_sort_list
  63.   (
  64.     /* sorted list to traverse */
  65.     const SORT_LIST *sl,
  66.     /* function to call.  the first parameter is the element being
  67.        visited.  the second parameter is supplied below.  this function
  68.        can change element keys if and only if the next operation to
  69.        be performed on the sorted list is a clear. */
  70.     int (*apply)(void *elem, void *param),
  71.     void *param,
  72.     /* if this flag non-zero, list is traversed in ascending order,
  73.        otherwise descending */
  74.     int forward,
  75.     /* key which indicates which element to start the traversal
  76.        with.  if forward flag set, start with least element greater
  77.        than or equal to this key.  if traversal is backward, start with
  78.        the greatest element less than or equal to this key.  if this
  79.        parameter is null, all elements are traversed. */
  80.     void *start_key
  81.   )
  82.   {
  83.     APPLY_PARAM ap;
  84.  
  85.     ap.apply = apply;
  86.     ap.param = param;
  87.     ap.first_branch = forward ? LESS_BRANCH : GREATER_BRANCH;
  88.     ap.start_key = start_key;
  89.     ap.k_e_compare = sl->key_elem_compare;
  90.  
  91.     return(do_apply(sl->tree, &ap));
  92.   }
  93.